{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Two Non-overlapping Sub-arrays Each With Target Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #binary-search #dynamic-programming #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #二分查找 #动态规划 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minSumOfLengths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找两个和为目标值且不重叠的子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>arr</code> 和一个整数值&nbsp;<code>target</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你在 <code>arr</code>&nbsp;中找 <strong>两个互不重叠的子数组</strong>&nbsp;且它们的和都等于&nbsp;<code>target</code>&nbsp;。可能会有多种方案，请你返回满足要求的两个子数组长度和的 <strong>最小值</strong> 。</p>\n",
    "\n",
    "<p>请返回满足要求的最小长度和，如果无法找到这样的两个子数组，请返回 <strong>-1</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [3,2,2,4,3], target = 3\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>只有两个子数组和为 3 （[3] 和 [3]）。它们的长度和为 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [7,3,4,7], target = 7\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>尽管我们有 3 个互不重叠的子数组和为 7 （[7], [3,4] 和 [7]），但我们会选择第一个和第三个子数组，因为它们的长度和 2 是最小值。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [4,3,2,6,2,3,4], target = 6\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>我们只有一个和为 6 的子数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [5,5,4,4,5], target = 3\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>我们无法找到和为 3 的子数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [3,1,1,1,5,1,2,1], target = 3\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>注意子数组 [1,2] 和 [2,1] 不能成为一个方案因为它们重叠了。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= arr[i] &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= target &lt;= 10^8</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-two-non-overlapping-sub-arrays-each-with-target-sum](https://leetcode.cn/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-two-non-overlapping-sub-arrays-each-with-target-sum](https://leetcode.cn/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,2,4,3]\\n3', '[7,3,4,7]\\n7', '[4,3,2,6,2,3,4]\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSumOfLengths(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        l = 0\n",
    "        total = 0\n",
    "        dp = [n + 1] * (n + 1)\n",
    "        ans = 3 * n + 1\n",
    "        for r in range(n):\n",
    "            total += arr[r]\n",
    "            while total > target:\n",
    "                total -= arr[l]\n",
    "                l += 1\n",
    "            \n",
    "            if total == target:\n",
    "                length = r - l + 1\n",
    "                ans = min(ans, length + dp[l])\n",
    "                dp[r + 1] = min(dp[r], length)\n",
    "            else:\n",
    "                dp[r + 1] = dp[r]\n",
    "        return ans if ans < n + 1 else -1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSumOfLengths(self, arr: List[int], target: int) -> int:\n",
    "        prefix_dp = [0 for _ in range(len(arr))]\n",
    "        suffix_dp = [0 for _ in range(len(arr))]\n",
    "        prefix_sum = [0 for _ in range(len(arr))]\n",
    "        suffix_sum = [0 for _ in range(len(arr))]\n",
    "        prefix_sum[0] = arr[0]\n",
    "        suffix_sum[-1] = arr[-1]\n",
    "        for i in range(1, len(arr)):\n",
    "            prefix_sum[i] = prefix_sum[i - 1] + arr[i]\n",
    "            suffix_sum[-i - 1] = suffix_sum[-i] + arr[-i - 1]\n",
    "        if prefix_sum[0] == target:\n",
    "            prefix_dp[0] = 1\n",
    "        else:\n",
    "            prefix_dp[0] = -1\n",
    "        for i in range(1, len(arr)):\n",
    "            right_idx = bisect.bisect_left(prefix_sum, prefix_sum[i] - target, 0, i - 1)\n",
    "\n",
    "            if prefix_sum[i] - target == prefix_sum[right_idx]:\n",
    "                cur_len = i - right_idx\n",
    "            elif prefix_sum[i] - target == 0:\n",
    "                cur_len = i + 1\n",
    "            else:\n",
    "                cur_len = -1\n",
    "            if cur_len == -1:\n",
    "                prefix_dp[i] = prefix_dp[i - 1]\n",
    "            else:\n",
    "                if prefix_dp[i - 1] > 0:\n",
    "                    if cur_len < prefix_dp[i - 1]:\n",
    "                        prefix_dp[i] = cur_len\n",
    "                    else:\n",
    "                        prefix_dp[i] = prefix_dp[i - 1]\n",
    "                else:\n",
    "                    prefix_dp[i] = cur_len\n",
    "        if suffix_sum[-1] == target:\n",
    "            suffix_dp[-1] = 1\n",
    "        else:\n",
    "            suffix_dp[-1] = -1\n",
    "        rev_suffix_sum = list(reversed(suffix_sum))\n",
    "        for i in range(1, len(arr)):\n",
    "            left_idx = bisect.bisect_left(rev_suffix_sum, rev_suffix_sum[i] - target, 0, i - 1)\n",
    "            if rev_suffix_sum[i] - target == rev_suffix_sum[left_idx]:\n",
    "                cur_len = i - left_idx\n",
    "            elif rev_suffix_sum[i] - target == 0:\n",
    "                cur_len = i + 1\n",
    "            else:\n",
    "                cur_len = -1\n",
    "            if cur_len == -1:\n",
    "                suffix_dp[-i - 1] = suffix_dp[-i]\n",
    "            else:\n",
    "                if suffix_dp[-i] > 0:\n",
    "                    if cur_len < suffix_dp[-i]:\n",
    "                        suffix_dp[-i - 1] = cur_len\n",
    "                    else:\n",
    "                        suffix_dp[-i - 1] = suffix_dp[-i]\n",
    "                else:\n",
    "                    suffix_dp[-i - 1] = cur_len\n",
    "        res = -1\n",
    "        for i in range(0, len(arr) - 1):\n",
    "            if prefix_dp[i] > 0 and suffix_dp[i + 1] > 0:\n",
    "                if res == -1:\n",
    "                    res = prefix_dp[i] + suffix_dp[i + 1]\n",
    "                else:\n",
    "                    res = min(res, prefix_dp[i] + suffix_dp[i + 1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def minSumOfLengths(self, arr: List[int], target: int) -> int:\n",
    "        acc = [0] + list(accumulate(arr))\n",
    "        \n",
    "        ans = inf\n",
    "\n",
    "        sl = SortedList()\n",
    "        min_diff = inf\n",
    "\n",
    "        for i, x in enumerate(acc):\n",
    "            while sl and sl[0][0] <= i:\n",
    "                min_diff = min(min_diff, sl[0][0] - sl[0][1])\n",
    "                sl.pop(0)\n",
    "\n",
    "            pos = bisect_left(acc, x + target)\n",
    "            if 0 <= pos < len(acc) and acc[pos] == x + target:\n",
    "                if min_diff != inf:\n",
    "                    ans = min(ans, min_diff + pos - i)\n",
    "                sl.add((pos, i))\n",
    "\n",
    "        return -1 if ans == inf else ans\n",
    "            \n",
    "\n",
    "        \n",
    "    \n",
    "        \n",
    "        return bisect_left(range(10 ** 5+1), True, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSumOfLengths(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        left = 0\n",
    "        right = 0\n",
    "        sum = 0\n",
    "        res = n + 1\n",
    "        res_list = []\n",
    "        while right < n:\n",
    "            while sum < target and right < n:\n",
    "                sum += arr[right]\n",
    "                right += 1\n",
    "            while sum > target and left < right:\n",
    "                sum -= arr[left]\n",
    "                left += 1\n",
    "            if sum == target:\n",
    "                res_list.append((right - left, left, right))\n",
    "                sum -= arr[left]\n",
    "                left += 1\n",
    "        res_list.sort(key=lambda x: x[0])\n",
    "        len_of_res_list = len(res_list)\n",
    "        long_list = []\n",
    "        for i in range(len_of_res_list - 1):\n",
    "            for j in range(len_of_res_list):\n",
    "                if long_list:\n",
    "                    if res_list[i][0] + res_list[j][0] >= min(long_list):\n",
    "                        return min(long_list)\n",
    "                if res_list[i][1] >= res_list[j][2] or res_list[i][2] <= res_list[j][1]:\n",
    "                    long_list.append(res_list[i][0] + res_list[j][0])\n",
    "        if not long_list:\n",
    "            return -1\n",
    "        return min(long_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSumOfLengths(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        l = r = s = 0\n",
    "        q = []\n",
    "        while r < n:\n",
    "            s += arr[r]\n",
    "            while s > target:\n",
    "                s -= arr[l]\n",
    "                l += 1\n",
    "            if s == target:\n",
    "                q.append((r - l + 1, l, r))\n",
    "            r += 1\n",
    "\n",
    "        q.sort(key=lambda x: x[0])\n",
    "        ans = n + 1\n",
    "        for i in range(len(q)):\n",
    "            for j in range(i + 1, len(q)):\n",
    "                if q[i][0] + q[j][0] >= ans:\n",
    "                    break\n",
    "                if q[i][1] > q[j][2] or q[j][1] > q[i][2]:\n",
    "                    ans = min(q[i][0] + q[j][0], ans)\n",
    "                    break\n",
    "        return -1 if ans > n else ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSumOfLengths(self, nums: List[int], target: int) -> int:\n",
    "        dic = {}\n",
    "        dic[0] = -1\n",
    "        sum = 0\n",
    "        res = inf\n",
    "        n = len(nums)\n",
    "        dp = [inf]*(n+1)\n",
    "        for i in range(n):\n",
    "            sum += nums[i]\n",
    "            dic[sum] = i\n",
    "            dp[i] = dp[i-1]\n",
    "            if sum-target in dic:\n",
    "                prePos = dic[sum-target]\n",
    "                length = i-prePos\n",
    "                dp[i] = min(dp[i],length)\n",
    "                if prePos!=-1:\n",
    "                    res = min(res,dp[prePos]+length)\n",
    "        if res==inf:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSumOfLengths(self, arr: List[int], target: int) -> int:\n",
    "        from itertools import accumulate\n",
    "        s = [0] + list(accumulate(arr))\n",
    "        n = len(s)\n",
    "        ans = inf \n",
    "        d = {0:0}\n",
    "        f = [inf]*n\n",
    "        for i,x in enumerate(s[1:],1):\n",
    "            f[i] = f[i - 1]\n",
    "            t = x - target\n",
    "            if t in d:\n",
    "                l = i - d[t]\n",
    "                f[i] = min(f[i],l)\n",
    "                if f[d[t]] != inf:\n",
    "                    ans = min(ans,l + f[d[t]])\n",
    "            d[x] = i \n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSumOfLengths(self, arr: List[int], target: int) -> int:\n",
    "        s = list(accumulate(arr, initial=0))\n",
    "        n = len(arr)\n",
    "        pair = []\n",
    "        for i in range(n):\n",
    "            l = s[i]\n",
    "            r = l + target\n",
    "            p = bisect_left(s, r)\n",
    "            if p >= len(s):\n",
    "                break\n",
    "            if s[p] == r:\n",
    "                pair.append([i, p - 1])  # [i, p - 1] 区间和为 target\n",
    "        if len(pair) <= 1:\n",
    "            return -1\n",
    "        minv = [inf] * n  # minv[i] 保持 arr[i+1]开始区间和为target的最小区间长度\n",
    "        curi = n - 1\n",
    "        curv = inf\n",
    "        for l, r in pair[::-1]:\n",
    "            while curi >= l:\n",
    "                minv[curi] = curv\n",
    "                curi -= 1\n",
    "            curv = min(curv, r - l + 1)\n",
    "        for i in range(l):\n",
    "            minv[i] = curv\n",
    "        ans = inf\n",
    "        for l, r in pair:\n",
    "            ans = min(ans, r - l + 1 + minv[r])\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSumOfLengths(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        prefix_min = [0] * n\n",
    "        suffix_min = [0] * n\n",
    "        d = {0: -1}\n",
    "        s = 0\n",
    "        min_l, min_r = 0, 1000000\n",
    "        for i in range(n):\n",
    "            s += arr[i]\n",
    "            if s - target in d and i - (d[s - target] + 1) < min_r - min_l:\n",
    "                min_l, min_r = d[s - target] + 1, i\n",
    "            prefix_min[i] = min_r - min_l + 1\n",
    "            d[s] = i\n",
    "        d = {0: n}\n",
    "        s = 0\n",
    "        min_l, min_r = 0, 1000000\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            s += arr[i]\n",
    "            if s - target in d and d[s - target] - 1 - i < min_r - min_l:\n",
    "                min_l, min_r = i, d[s - target] - 1\n",
    "            suffix_min[i] = min_r - min_l + 1\n",
    "            d[s] = i\n",
    "        ans = 1000000\n",
    "        for i in range(n - 1):\n",
    "            ans = min(ans, prefix_min[i] + suffix_min[i + 1])\n",
    "        return ans if ans < 1000000 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSumOfLengths(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        pre, hs, st = [0],{0:0},[]\n",
    "        for a in arr: pre.append(pre[-1]+a)\n",
    "        for i in range(n):\n",
    "            if pre[i+1]-target in hs:\n",
    "                j = hs[pre[i+1]-target]\n",
    "                st.append((j,i))\n",
    "            hs[pre[i+1]] = i+1\n",
    "        ans,m,j = float(\"inf\"),len(st),len(st)-1\n",
    "        if m <2: return -1\n",
    "        mini = [st[0][1]-st[0][0]+1]\n",
    "        for i in range(1,m):\n",
    "            mini.append(min(mini[-1],st[i][1]-st[i][0]+1))\n",
    "        for i in range(m-1,0,-1):\n",
    "            while j>=0 and st[i][0]<=st[j][1]:\n",
    "                j-=1\n",
    "            if j>=0: ans = min(ans,st[i][1]-st[i][0]+1+mini[j])\n",
    "        return ans if ans!=float(\"inf\") else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSumOfLengths(self, arr: List[int], target: int) -> int:\n",
    "        presum = [0] + arr\n",
    "        dp = [len(arr)+1] * (len(arr)+1)\n",
    "        for i in range(len(arr)):\n",
    "            presum[i+1] += presum[i]\n",
    "\n",
    "        target_dic = {0: 0}\n",
    "        res_target = []\n",
    "\n",
    "        for i, cur_sum in enumerate(presum):\n",
    "            if cur_sum - target in target_dic:\n",
    "                res_target.append([target_dic[cur_sum-target], i-1])\n",
    "                dp[i] = i - target_dic[cur_sum-target]\n",
    "            target_dic[cur_sum] = i\n",
    "        \n",
    "        for i in range(len(arr)):\n",
    "            dp[i+1] = min(dp[i], dp[i+1])\n",
    "\n",
    "        # print(target_dic)\n",
    "        # print(res_target)\n",
    "        # print(dp)\n",
    "\n",
    "        if len(res_target) <= 1:\n",
    "            return -1\n",
    "        \n",
    "        ans = inf\n",
    "        for [a, b] in res_target:\n",
    "            tmp_len = b - a + 1\n",
    "            if dp[a] < len(arr)+1:\n",
    "                ans = min(ans, tmp_len+dp[a])\n",
    "        \n",
    "        return ans if ans < inf else -1\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSumOfLengths(self, arr: List[int], target: int) -> int:\n",
    "        # prefix sum + hash\n",
    "        prefix_sum = []\n",
    "        N = len(arr)\n",
    "\n",
    "        for i in range(N):\n",
    "            if not prefix_sum:\n",
    "                prefix_sum.append(arr[i])\n",
    "            else:\n",
    "                prefix_sum.append(arr[i]+prefix_sum[-1])\n",
    "\n",
    "        lookup = {}\n",
    "        for i in range(N):\n",
    "            lookup[prefix_sum[i]] = i \n",
    "\n",
    "        res = []\n",
    "        for i in range(N):\n",
    "            if target == prefix_sum[i]:\n",
    "                res.append([0,i])\n",
    "            if prefix_sum[i]+target in lookup.keys():\n",
    "                res.append([i+1,lookup[prefix_sum[i]+target]])\n",
    "        \n",
    "        res.sort()\n",
    "\n",
    "        one_min = [0]*N \n",
    "        two_min = sys.maxsize \n",
    "\n",
    "        for x,y in res:\n",
    "            dlt = y-x+1\n",
    "            one_min[y] = dlt\n",
    "            \n",
    "\n",
    "        pivot = 0\n",
    "        for i in range(N):\n",
    "            if one_min[i] != 0:\n",
    "                if pivot != 0:\n",
    "                    one_min[i] = min(pivot, one_min[i])\n",
    "                pivot = one_min[i]\n",
    "            else:\n",
    "                one_min[i] = pivot\n",
    "\n",
    "\n",
    "        for x,y in res:\n",
    "            dlt2 = y-x+1\n",
    "            if x > 0:\n",
    "                dlt1 = one_min[x-1]\n",
    "                if dlt1 > 0:\n",
    "                    two_min = min(two_min, dlt1+dlt2)\n",
    "\n",
    "        if two_min == sys.maxsize:\n",
    "            return -1\n",
    "        return two_min\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSumOfLengths(self, arr: List[int], target: int) -> int:\n",
    "        presum = [0]\n",
    "        for num in arr:\n",
    "            presum.append(presum[-1] + num)\n",
    "\n",
    "        # my_dict记录的是从i 到 dict[i] 位置的线段和为target\n",
    "        my_dict = {}\n",
    "        # list用来记录这个数对\n",
    "        pos_list = []\n",
    "        for i, v in enumerate(presum):\n",
    "            if v - target in my_dict:\n",
    "                pos_list.append((my_dict[v - target], i))\n",
    "            my_dict[v] = i\n",
    "\n",
    "        pos_list.sort(key = lambda x:(x[0], x[1]))\n",
    "\n",
    "        res = inf\n",
    "        cur = inf\n",
    "        n = len(pos_list)\n",
    "        length = [0] * n\n",
    "        start_list = [s for s, e in pos_list]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            # 从后往前去找满足条件的子串的开始，并算出在现在这个开始之后的子串中，长度最小的是多少\n",
    "            cur = min(cur, pos_list[i][1] - pos_list[i][0])\n",
    "            # 记录这个长度\n",
    "            length[i] = cur\n",
    "            # 二分找出现在这个子串右侧的左端点在哪里\n",
    "            idx = bisect.bisect_left(start_list, pos_list[i][1])\n",
    "            if idx < n:\n",
    "                # 如果这个右侧左端点合法，\n",
    "                res = min(res, pos_list[i][1] - pos_list[i][0] + length[idx])\n",
    "\n",
    "        return res if res != inf else -1\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSumOfLengths(self, arr: List[int], target: int) -> int:\n",
    "        total = sum(arr)\n",
    "        if target*2 > total:\n",
    "            return -1\n",
    "        record = {0:-1}\n",
    "        # 左开右闭区间\n",
    "        stack = []\n",
    "        cur = 0\n",
    "        for i,j in enumerate(arr):\n",
    "            cur += j\n",
    "            if cur - target in record:\n",
    "                stack.append([record[cur-target],i])\n",
    "            record[cur]= i\n",
    "        m = len(stack)\n",
    "        if m < 2:\n",
    "            return -1\n",
    "        ans = inf\n",
    "        queue = []\n",
    "        for i,j in stack:\n",
    "            heappush(queue,[j-i,i])\n",
    "        for i,j in stack:\n",
    "            while queue and queue[0][1] < j:\n",
    "                heappop(queue)\n",
    "            if queue:\n",
    "                ans = min(ans,j-i+queue[0][0])\n",
    "        return ans if ans != inf else -1   \n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSumOfLengths(self, arr: List[int], target: int) -> int:\n",
    "        pre, post = 0, 0\n",
    "        presta, poststa = {0:-1}, {0:len(arr)}\n",
    "        presum, postsum = [float('inf')] * len(arr), [float('inf')] * len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            pre += arr[i]\n",
    "            post += arr[-i-1]\n",
    "            if pre - target in presta:\n",
    "                presum[i] = i - presta[pre-target]\n",
    "            if post - target in poststa:\n",
    "                postsum[-i-1] = poststa[post-target] - (len(arr)-i-1)\n",
    "            presta[pre], poststa[post] = i, len(arr)-i-1\n",
    "        for i in range(1, len(arr)):\n",
    "            if presum[i] > presum[i-1]:\n",
    "                presum[i] = presum[i-1]\n",
    "            if postsum[-i-1] > postsum[-i]:\n",
    "                postsum[-i-1] = postsum[-i]\n",
    "        minval = float('inf')\n",
    "        for i in range(len(arr)-1):\n",
    "            if presum[i] + postsum[i+1] < minval:\n",
    "                minval = presum[i] + postsum[i+1]\n",
    "        if minval == float('inf'): return -1\n",
    "        else: return minval"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSumOfLengths(self, nums: List[int], target: int) -> int:\n",
    "        maps = {}\n",
    "        n = len(nums)\n",
    "        temp = 0\n",
    "        lrs = []\n",
    "        for i in range(n):\n",
    "            temp += nums[i]\n",
    "            maps[temp] = i\n",
    "            ex = temp-target\n",
    "            if ex in maps:\n",
    "                lrs.append([maps[ex]+1, i])\n",
    "            if temp == target:\n",
    "                lrs.append([0, i])\n",
    "        if len(lrs) < 2:\n",
    "            return -1\n",
    "        lrs.sort(key = lambda x: x[1])\n",
    "        rs = []\n",
    "        for lr in lrs:\n",
    "            rs.append(lr[1])\n",
    "        n = len(lrs)\n",
    "        f = [[0]*3 for _ in range(n)]\n",
    "        f[0][1] = lrs[0][1]-lrs[0][0]+1\n",
    "        f[0][2] = float('inf')\n",
    "        for i in range(1, n):\n",
    "            f[i][1] = min(lrs[i][1]-lrs[i][0]+1, f[i-1][1])\n",
    "            f[i][2] = float('inf')\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            l = lrs[i][0]\n",
    "            idx = bisect.bisect_left(rs, l)\n",
    "            if l > rs[idx]:\n",
    "                f[i][2] = min(f[i-1][2], f[idx][1]+lrs[i][1]-lrs[i][0]+1)\n",
    "            elif l <= rs[idx] and idx > 0:\n",
    "                f[i][2] = min(f[i-1][2], f[idx-1][1]+lrs[i][1]-lrs[i][0]+1)\n",
    "        if f[n-1][2] == float('inf'):\n",
    "            return -1\n",
    "        \n",
    "        return f[n-1][2]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSumOfLengths(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        s = 0\n",
    "        idx = {0: 0}\n",
    "        a = {}\n",
    "        for i in range(n):\n",
    "            s += arr[i]\n",
    "            idx[s] = i + 1\n",
    "            t = s - target\n",
    "            try:\n",
    "                p = idx[t]\n",
    "            except KeyError:\n",
    "                continue\n",
    "            a[i] = [p, i]\n",
    "\n",
    "        dp = [[10 ** 9] * 2 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][0] = dp[i - 1][0]\n",
    "            dp[i][1] = dp[i - 1][1]\n",
    "            if i in a:\n",
    "                cost = a[i][1] - a[i][0] + 1\n",
    "                dp[i][0] = min(dp[i][0], cost)\n",
    "                if a[i][0] - 1 >= 0:\n",
    "                    dp[i][1] = min(dp[i][1], cost + dp[a[i][0] - 1][0])\n",
    "        ans = dp[n - 1][1]\n",
    "        if ans == 10 ** 9:\n",
    "            ans = -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSumOfLengths(self, arr: List[int], target: int) -> int:\n",
    "        n=len(arr)\n",
    "        dp_cur=[0]*n  #以当前数结尾的最短子数组\n",
    "        dp=[0]*n #到当前的最短子数组\n",
    "        presum=collections.defaultdict(list)\n",
    "        cur_sum=0\n",
    "        presum[0]=[-1]\n",
    "        ans=inf\n",
    "\n",
    "        for i,num in enumerate(arr):\n",
    "            cur_sum+=num\n",
    "            if presum[cur_sum-target]:\n",
    "                k=presum[cur_sum-target][-1]\n",
    "                dp_cur[i]=i-k\n",
    "                dp[i]=min(i-k,dp[i-1]) if i>=1 and dp[i-1]>0 else i-k\n",
    "                if k>0 and dp[k]>0:\n",
    "                    ans=min(ans,dp[k]+i-k)\n",
    "            else:\n",
    "                if i>=1:\n",
    "                    dp[i]=dp[i-1]\n",
    "            presum[cur_sum].append(i)\n",
    "\n",
    "        if ans==inf:\n",
    "            return -1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSumOfLengths(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        sums = [0] * (n + 1)\n",
    "        idx = {0: 0}\n",
    "        for i in range(n):\n",
    "            sums[i + 1] = sums[i] + arr[i]\n",
    "            idx[sums[i + 1]] = i + 1\n",
    "\n",
    "        a = {}\n",
    "        for i in range(1, n + 1):\n",
    "            t = sums[i] - target\n",
    "            try:\n",
    "                p = idx[t]\n",
    "            except KeyError:\n",
    "                continue\n",
    "            a[i - 1] = [p, i - 1]\n",
    "\n",
    "        dp = [[10 ** 9] * 2 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][0] = dp[i - 1][0]\n",
    "            dp[i][1] = dp[i - 1][1]\n",
    "            if i in a:\n",
    "                cost = a[i][1] - a[i][0] + 1\n",
    "                dp[i][0] = min(dp[i][0], cost)\n",
    "                if a[i][0] - 1 >= 0:\n",
    "                    dp[i][1] = min(dp[i][1], cost + dp[a[i][0] - 1][0])\n",
    "        ans = dp[n - 1][1]\n",
    "        if ans == 10 ** 9:\n",
    "            ans = -1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSumOfLengths(self, arr: List[int], target: int) -> int:\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if j == 2:\n",
    "             return 0\n",
    "          if i == n:\n",
    "             return inf\n",
    "          res = dfs(i + 1, j)\n",
    "          for y in g[i]:\n",
    "             res = min(res, dfs(y + 1, j + 1) + y - i + 1)\n",
    "          return res\n",
    "       \n",
    "       n = len(arr)\n",
    "       g = [[] for _ in range(n)]\n",
    "       i = 0\n",
    "       j = 0\n",
    "       s = 0\n",
    "       while j < n:\n",
    "          s += arr[j]\n",
    "          while s > target:\n",
    "             s -= arr[i]\n",
    "             i += 1\n",
    "          if s == target:\n",
    "             g[i].append(j)\n",
    "          j += 1\n",
    "       res = dfs(0, 0)\n",
    "       return res if res < inf else -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
